'''
冒泡排序：
第一个元素和右边所有元素对比，找到最大/小的元素，交换位置，直到所有完成。
'''

def insertion_sort(arr):
    # 生成1~n
    for i in range(len(arr)):
        # 获取左边索引
        preIndex = i-1
        # 获取当前位置
        current = arr[i]
        # 找到左边比自己小的，那么就放到其后面。
        while preIndex >= 0 and arr[preIndex] > current: ## 前面比自己大
            arr[preIndex+1] = arr[preIndex] # 把前面一个后移一个位置
            preIndex-=1 # 再往前找
        # 找到一个最佳位置，插入。
        arr[preIndex+1] = current
    return arr

def test_insertion_sort():
    # 测试示例 1
    arr = [64, 34, 25, 12, 22, 11, 90]
    assert insertion_sort(arr) == [11, 12, 22, 25, 34, 64, 90], "测试示例 1 失败"
    
    # 测试示例 2: 已经有序的列表
    arr = [1, 2, 3, 4, 5]
    assert insertion_sort(arr) == [1, 2, 3, 4, 5], "测试示例 2 失败"
    
    # 测试示例 3: 逆序列表
    arr = [5, 4, 3, 2, 1]
    assert insertion_sort(arr) == [1, 2, 3, 4, 5], "测试示例 3 失败"
    
    # 测试示例 4: 包含重复元素的列表
    arr = [4, 2, 2, 8, 3, 3, 1]
    assert insertion_sort(arr) == [1, 2, 2, 3, 3, 4, 8], "测试示例 4 失败"
    
    # 测试示例 5: 空列表
    arr = []
    assert insertion_sort(arr) == [], "测试示例 5 失败"
    
    # 测试示例 6: 只有一个元素的列表
    arr = [1]
    assert insertion_sort(arr) == [1], "测试示例 6 失败"
    
    print("所有测试用例通过！")

# 运行测试
test_insertion_sort()